public class heapSort {


    public void headSort(int[] arr) {
        //1.排升序，建大根堆
        create(arr);
        int end = arr.length - 1;
        while(end > 0) {
            //2.每次交换堆顶和最后一个元素
            swap(arr,0,end);
            //3.交换完调整
            siftDown(arr,0,end);
            end--;
        }
    }
    /**
     * 交换
     */
    public void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public void create(int[] arr) {
        //从最后一棵子树向下调整
        for (int parent = (arr.length -1-1)/2; parent >= 0 ; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }
    /**
     *  向下调整
     */
    public void siftDown(int[] arr,int parent,int len) {
        int child = parent*2 + 1;
        while(child < len) {
            //1.找左右孩子最大的
            if(child+1 < len && arr[child+1] > arr[child]) {
               child = child + 1;
            }
            if(arr[child] > arr[parent]) {
                swap(arr,child,parent);
                parent = child;
                child = parent*2 + 1;
            }else {
                break;
            }

        }
    }


}
